package mystack;

import org.w3c.dom.Node;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

public class MyStack <T>{
    T[] elem;
    int usedSize;

    public MyStack(int k) {
        this.elem = (T[])new Object[k];
    }
    public T push(T e){
        if(elem.length==usedSize){
            ensureCapacity();
        }
        elem[usedSize]=e;
        usedSize++;
        return e;
    }
    public T pop(){
        if(empty()){
            System.out.println("stack is empty,can not pop");
            return null;
        }else{
            T tmp=elem[usedSize-1];
            usedSize--;
            return tmp;
        }
    }
    public T peek(){
        if(empty()){
            System.out.println("stack is empty,can not pop");
            return null;
        }else{
            return elem[usedSize-1];
        }
    }
    public int size(){
        return usedSize;
    }
    public boolean empty(){
        return usedSize==0;
    }
    private void ensureCapacity(){
        elem= Arrays.copyOf(elem,2*elem.length);
    }
    /*private static class ListNode<T>{
        T val;
        ListNode<T> next;
        ListNode<T> prev;
    }*/
    public void printReverseListByStack(LinkedList linkedList){
        MyStack<T> stack=new MyStack<>(10);
        for (Object x:linkedList){
            stack.push((T)x);
        }

        while(!stack.empty()){
            System.out.print(stack.pop()+" ");
        }
    }

    /**
     * 括号匹配问题
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            Character c=s.charAt(i);
            if(c=='('||c=='['||c=='{'){
                stack.push(c);
            }else{
                if(stack.empty()){
                    return false;
                }else{
                    switch (c){
                        case ')':
                            if(stack.pop()!='('){
                                return false;
                            }
                            break;
                        case ']':
                            if(stack.pop()!='['){
                                return false;
                            }
                            break;
                        case '}':
                            if(stack.pop()!='{'){
                                return false;
                            }
                            break;
                    }
                }
            }
        }
        if(stack.empty())
            return true;
        else
            return false;
    }
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if(!IsOperation(tokens[i])){
                stack.push(Integer.parseInt(tokens[i]));
            }else{
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (tokens[i]){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.peek();
    }
    private boolean IsOperation(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }else{
            return false;
        }
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> s=new Stack<>();
        int i=0;
        int j=0;
        for (; i < pushV.length; i++) {
            s.push(pushV[i]);
            while(!s.empty()&&s.peek()==popV[j]){
                s.pop();
                j++;
            }
        }
        if(s.empty()){
            return true;
        }else{
            return false;
        }
    }
}


